\chapter{Assembleur}

	Il s'agit de reconstituer une liste de consensus les plus grands possibles en étendant les séquences de nucléotides.
	La liste entière est parcourue en comparant deux à deux les séquences et en les assemblant lorsque c'est possible.
	Ce parcours sera effectué 100 fois au maximum. Après chaque itération un histogramme de la taille des séquences est généré. Pour cela, les fréquences sont écrites dans un fichier de données, après l'execution du programme les histogrammes peuvent être tracés à l'aide d'un script \emph{gnuplot}.

	Une comparaison entre histogrammes est faite après chaque itération afin de vérifier si la taille des séquences augmente ou stagne. Nous avons choisi de faire cette comparaison le plus souvent possible car la géneration d'histogramme est peu coûteuse en regard du coût d'une itération. Le programme est interompu dès qu'il y a stagnation afin de réduire le temps d'exécution au minimum nécessaire.


\section{Mécanisme de blocs}

	Le parcours de la matrice peut être effectué par blocs de lignes répartis entre les différents processus MPI ou thread OpenMP. Le découpage proposé peut être réalisé simplement en OpenMP à l'aide de la directive suivante:
	\begin{verbatim}
#pragma omp parallel for schedule(dynamic, h)
	\end{verbatim}
Où \emph{h} est le nombre de lignes par bloc.\\

	Ceci permet d'obtenir une charge bien répartie pour un \emph{overhead} minimal sans faire de manipulation compliquée d'indices de boucles.


\section{Calcul des extensions}
	Le principe est de comparer deux séquences d'Adn en vérifiant si les n-1 avant derniers nucléotides de la 2ème séquence correspondent aux n-1 derniers nucléotides de la 1ère séquence. Dans ce cas, la dernière lettre de la 2ème séquence est ajoutée à la 1ère séquence. Les flags de marquage d'utilisation de la séquence sont marqués à 1, et les longueurs sont mises à jour.

\section{Gestion des listes de séquences}

	Une fonction permet de fusionner deux listes en copiant les éléments d'une liste dont le flag d'assemblage n'est pas marqué, à la fin de l'autre liste. Une autre fonction permet d'effacer une liste pour sa réutilisation éventuelle en enlevant les anciennes données contenues.

